Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Algorithms, Fall22, Bowdoin College

Syllabus (csci 2200, Fall 2022)

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

Class times:

  • Section A: MW 10:05-11:30, lab Thu 1:15-2:45
  • Section B: TR 11:40-13:05, lab Thu 2:45 - 4:15

Classroom: classes in Searles 126, labs in VAC South 303

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]

Prerequisites: csci 2101 (Data Structures)

Practically speaking, we’ll spend the first week reviewing problems and concepts from Data Structures, such as linear search and binary search, big-oh, best cases and worst cases. While diving deeper into analysis we’ll encounter logarithms and exponents. If you have not seen these in a long time, expect to spend more time the first weeks of classes.

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?

Weekly flow: How will this class work?

The class meets three times a week (2 x class meetings plus the weekly lab). Each week we’ll focus on a topic (or a couple of topics). Roughly speaking, the class meetings are dedicated to going over the new content and the lab is for working on a set of problems that reinforce and extend the topics seen that week.

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 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!

Here’s the weekly flow:

  1. Pre-view the lecture notes. 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 lectures. Time to budget: .5 hour

  2. Attend classes and the lab. Come to class, understand the details, get your questions answered and work with your peers. Time to budget: 4.5 hours.

  3. Complete the weekly assignment. Work alone or with your partner to complete the weekly assignment. Drop in to one or more of the study groups/office hours to check on your ideas and get your questions answered. Turn it in on Gradescope. Time to budget: 3-4 hours.

  4. Take the weekly quiz. Review that week’s material, including lecture notes, slides, the lab problems and their solutions. When you are ready, take the weekly quiz. The quizzes are available on Canvas, and you’ll take them remotely. Most quizzes are automatically graded, and consist of multiple-choice/short answer questions. Most quizzes are capped at 120 minutes to avoid time pressure, but they take on the order of 30 minutes or less to complete. Time to budget: 2-3 hours.

Time Commitment

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

Some of you will put in more or less time than what I suggested above. 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, take a look at the optional problems or just send me an email and I will happily provide additional problems.

Grading Policy

The work for the class throughout the semester consists of:

  • Quizzes: 30% There will be a total of O(10) online quizzes. The quizzes are administered at this time via Canvas and are a combination of multiple-choice and short-answer questions that test the fundamental knowledge from lectures and labs. Expect them to be short and focused on the specific topic discussed that week. You’ll take the quizzes remotely from your room. All quizzes are weighed equally (although the number of questions in each will be different).

  • Assignments: 40% There are a total of O(10) 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: 30% 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 10%).

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.

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 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.

Key Tips

You will find this class to be difficult, especially in the second half. What makes it hard is that the material is theoretical and spans many levels of abstraction, and that 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. Working on an algorithms assignment will seem easier than working on a programming assignment in Data Structures (argh, those bugs). When you write code, the process of getting your code to work forces you to correct your logic until it is correct and the program does what it’s supposed to do. When you come up with 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 work partially. The hard part will be coming up with an algorithm that is fully 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. 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.

  • 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!