Syllabus

Instructor: Laura Toma, email: ltoma at bowdoin.edu, office: Searles 219

Class time: TR 10:05-11:30, lab Fri 11:40-1:05

Classroom: classes in Searles 126, labs in VAC North 304

Prerequisites: csci 2101 (Data Structures)

Algorithms are the backbone of computer science. Everywhere computer sciences reaches, there is an algorithm. This class is an introduction to critical thinking and problem solving through the design and analysis of algorithms. Throughout the course we will consider fundamental computational problems and their algorithmic solutions. We’ll illustrate the process of coming up with algorithms, analysing their theoretical complexity, and arguing that they work correctly. Overall the class will show that the “…subject of algorithms represents a powerful lens through which to view the field of computer science in general” [Kleinberg & Tardos]

Learning goals: After taking this class you will be able to:

  1. Demonstrate understanding of fundamental computational problems and the algorithms proposed to solve them
    1. Illustrate how these algorithms work
    2. Analyze their theoretical complexity
    3. Use them as building blocks in other algorithms
  2. Demonstrate understanding of fundamental algorithmic design techniques (recursion, divide-and-conquer, greedy, dynamic programming)
  3. Demonstrate the ability to design efficient algorithms for new problems
    1. Come up with ideas
    2. Argue whether they are correct (correctness justification) or incorrect (come up with counter-examples)
    3. Analyze their theoretical complexity and compare them
    4. Consider the question: Can the solution be improved?

Lectures, labs and the weekly flow: The class meets twice a week for lecture, and once a week for lab. Generally speaking, the classes are dedicated to going over fundamental algorithms and techniques, and the labs are for applying and extending the conceps from class and working on new problems.

Preview: Each week, before coming to class, read the lecture notes for that week. It is expected that you understand the big ideas and results ahead of that week’s class. This will make the classes more effective and interactive and will allow time to sprinkle problems.

Labs: The lab problems are meant to be solved in class, during the lab. Myself and the LAs will be around to work with you, facilitate discussions and answer questions. The labs are there to help you reinforce and extend the concepts while you collaborate freely with your peers and talk to us. Labs are not graded, however it is important that you strive to understand all the problems as they are designed to extend the lectures. It is your responsibility to complete the lab problems and get your questions answered. Overall, labs should be fun and you’ll find that most of your learning occurs while you work on the lab with your peers!

Classes and the labs, together, prepare you for the weekly assignments, which consist of new problems.

Work and Grading Policy:

  • Quizzes: 20% In the first weeks of the semester while learning analysis tools, I have created a set of weekly quizzes to support learning. Expect them to be short and focused on the specific topic discussed that week. The quizzes are available on Canvas, and you’ll take them remotely from your room. They are self-graded. There will be a total of 8 online quizzes and are all weighed equally (although the number of questions in each will be different).

  • Assignments: 40% There will be a total of 10-12 assignments throughout the semester, roughly one per week. The assignments consist of new problems, for which you’ll have to come up with efficient solutions. An important goal of the assignments is to develop good algorithmic writing style — your solutions need to look professional, neat, easy to understand, explained, justified and analyzed. All assignments are weighed equally.

  • Exams: 40% There will be 3 in-class exams: the first one in in week 6, the second one in week 10 and the last one at the end of the semester (check Polaris for the final exam slot for this class). The exams are non-cumulative, to the extent that it’s possible. All exams weighed equally (i.e. each exam 13.3%).

  • Class engagement: This means attending class, working with your group in the lab, asking questions, engaging in discussions, volunteering answers, participating on Slack, attending office hours and striving to turn in good work. Overall engagement will be used as a tie breaker when your score is between two grades.

Time Commitment: This is a core CS class and will demand a significant time commitment. It is critical that you budget your time accordingly. You should expect to commit 10 hours a week to meet the expectations of the course, and more to excel. The actual time you spend on the class will vary from week to week as some topics—esp towards the middle of the semester—will be harder and may take more hours.

Some of you will put in more or less time than suggested. That is normal. If you find that you struggle with discrete math (e.g. logarithms, exponents, etc) you will need to allocate more time to grasp those concepts — hang in there, you just need more practice. If you finish faster, use the time to work on the challenge problems provided with each lab.

What you can expect from me:

My goal is to teach a class that’s similar to algorithms classes at peer institutions. The syllabus is packed and you will find the pace and the problems ocasionally challenging. Many of the problems in labs and assignments come from algorithms classes at other universities (such as Stanford, MIT, Berkeley, etc). Speaking of that, I am a big fan of and grateful for open resources, and this is the reason I keep this website on github rather than behind Canvas. Some of you will go on to software engineering careers where a strong algorithmic background is a must. Many of you will go through technical interviews which draw heavily from the content of this class. It is important to pack many topics in the syllabus and expose you to challenging new problems. Ultimately the goal of the class is to give you the tools so that you can solve new problems on your own. A strong algorithmic backgound will elevate your analytical and abstraction skills and will be a big advantage to your career path, whatever it might be.

My teaching style is to create a friendly, open atmosphere where everyone feels comfortable and motivated to learn. There are no stupid questions. Any question is a sign that you want to engage. Based on my experience, the most effective learning happens when YOU (the class) work well together. Open collaboration in the lab will be highly encouraged. Assignments are pair-optional, although everyone is highly encouraged to find a partner. To support everyone’s learning at their own pace I have created detailed lecture notes and an ample set of supporting study questions, practice problems and quizzes, many with solutions. Please help me make this class great by staying engaged and by giving me feedback (even if I don’t ask for it)! Feedback is always welcome.

I know there are circumstances in our lives that we can’t control. If you have any (significant) circumstances that make learning hard, just talk to me, and we will figure something out.

Tips:

You will find this class to be difficult. What makes it difficult is not the algorithms we discuss in class (though there will be a few that are quite brilliant). What makes it difficult is the creative part, the problem solving, the coming up with new algorithms for new problems. The material is theoretical and spans many levels of abstraction, and coming up with algorithms is both an art and a science: there is no systematic way to have an idea, and problems that seem very similar, may have very different solutions. Every problem is “new”.

2101 vs 2200: Working on an algorithms assignment will seem easier than working on a programming assignment in Data Structures (argh, those bugs).

  • 2101: When you write code, the process of getting your code to work forces you to correct your logic until the program does what it’s supposed to do.

  • 2200: When you write pseudocode for an algorithm, you have to rely on yourself to think through all its details carefully; you need to figure out if it has bugs without implementing it. Thinking through your idea and all the cases that might happen — it all happens in your head. There is no computer to tell you that you have bugs, that your logic has holes, YOU need to do that. In this class it will be easy to come up with algorithms that almost work . The hard part will be coming up with an algorithm that are actually correct (and efficient). That’s the beauty of it!

Here are some suggestions for doing well :

  • Budget your time and give yourself plenty of time to read the materials and work on the assignments each week. Take the labs seriously. Plan on at least 10 hours a week, and make a schedule which you follow every week.

  • Be pro-active about things that are not clear. There’s a lot of helpful free resources out there. Just search on the Internet (really, that’s allowed encouraged).

  • Self-reflection: Try to formulate questions, and try to answer them yourself.

  • Find a group of peers to work with. Explain your ideas, and listen to theirs. Try to argue why an idea is correct, or try to prove it wrong by finding an instance where it does not work.

  • Go to the study groups/office hours and talk to myself and the TAs; Listen to your peers’ questions and get your questions answered. Solve all problems that are assigned, even those that are optional.

  • If you are Math-CS double major, you probably wish the class was more rigorous. Check out the lecture notes or a textbook for proofs. Many correctness justifications rely on induction, so if you’ve seen that, use this opportunity to come up with those proofs yourself (we’ll skip them in class)

  • Don’t be harsh on yourself if you are not doing as well as you expected. It takes time to learn, and often we learn (more) from mistakes!