Link Search Menu Expand Document
CSCI 2200, Fall '21

Algorithms, Fall 2021, Bowdoin College

Instructor: Laura Toma

Meeting time: Mon, Wed & Fri 10:05-11:30am

Where: Searles 126 Searles 223

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. Arguing why an algorithm works is a crucial part of algorithmic problem solving, which we’ll approach only intuitively without going into rigorous proofs (for those who have the background of Intro to math reasoning extending these ideas to formal arguments should be easy). 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)

Learning Goals

By the end of this course, you should be able to:

  1. Demonstrate understanding of fundamental computational problems and the algorithms that were proposed to solve them
    1. Illustrate how these algorithms work
    2. Analyze their theoretical complexity
    3. Use them as building blocks to design algorithms for new problems
  2. Demonstrate understanding of fundamental algorithmic design techniques (recursion, divide-and-conquer, greedy and dynamic programming)
  3. Understand and apply the process of designing efficient algorithms
    1. Come up with ideas
    2. Argue whether they are correct or incorrect (come up with counter-examples)
    3. Analyze their theoretical complexity and compare them
    4. Ask: Can we do better?
  4. Demonstrate the ability to design and analyze algorithms for new problems

Getting Ready for the Course

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. If you are not sure what these mean, you probably want to go back and review them in order to make the beginning of the class smoother.
In the first 3 weeks we’ll dive deeper into analysis, which means we’ll encounter logarithms and exponents. If you have not seen these in a long time, it’s a good idea to review them. These are all fundamental concepts and there are plenty of resources around.

Weekly flow: How will this class work?

The class meets (in-person) three times a week. Each week we’ll focus on a couple of topics. To this end there will be lectures (both recorded and in-person), lecture notes, exercises, slides and a problem set.

Roughly speaking, the first two meetings of the week are dedicated to going over the new content. The third weekly meeting, designated as the lab, is for working on the problem set. The lab problems are meant to be solved in class, during the lab. Myself and the TAs/LAs will be around to work with you, facilitate discussions and answer your questions. The labs are not graded. It is your responsibility to complete the lab problems and check in with us.

Here’s the weekly timeline:

  1. Pre-view the lecture notes and take the pre-meeting check. Each week, before coming to class, your first task is to read the lecture notes for that week. It is expected that you understand the big ideas and results ahead of that week’s lectures. Each week, before coming to class, you need to take the pre-meeting check. The pre-check is online and consists of a set of easy multiple-choice questions; it covers very basic questions from the lecture. You need to take the pre-check before attending the first weekly meeting. The pre-checks are set so that you have 3 attempts and it will retain the highest score. It is open books and no time limit.

    • Time to budget: 2 hours

  2. Attend the 3 weekly meetings. Come to class, work with your peers, and get your questions answered. The pace of the in-class presentation will be fast since everyone will be familiar with the content. This will leave more time to work on problems! Answers to the lab will be posted at the end of the lab.

    • Time to budget: 4.5 hours.

  3. Review material and take the weekly quiz. Review the week’s material, including lecture notes, slides, the lab problems and their solutions; use the self-study quizzes and the study questions to help evaluate your understanding. Drop in to virtual office hours, help sessions/ study groups to get your questions answered. When you are ready, take the weekly quiz.

    • Time to budget: 2-3 hours.

  4. Work on the current assignment. Work on the current assignment.

    • Time to budget: 2 hours.

Work and Grading Policy

The work for the class, throughout the semester, consists of:

  • Pre-checks: There are a total of 12 pre-checks (approx. one per week). These checks are very easy, open books, unlimited time, 3 attempts; their goal is simply to help you stay on track (preview the notes before coming to class every week).

  • Labs: There are a total of 15 labs (one every week). The weekly lab consist of a problem set focused on the topics discussed that week. The lab problems are meant to be finished in class, during the designated lab time, working with a small group. Labs are not graded.
    • Don’t be surprised if you’ll find that most of your learning occurs while you work on the lab with your peers!

  • Quizzes: There are a total of 14 quizzes (one per week). The quizzes are administered via Blackboard/Gradescope, and are a combination of multiple-choice and short answer questions. Expect them to be short and focused on the specific topic discussed that week. Some of these quizzes will be in class, others will be take home.

  • Assignments: There are a total of 7 assignments throughout the semester (one every two weeks). Each assignment consists of O(1) problems for which you will be asked to come up with efficient algorithms. Expect the problems in the assignments to be hard, but fun.

  • Exams: There are no exams.

The final grade will be computed based on the 12 pre-checks , 14 quizzes and 7 assignments as follows:

  • Pre-checks: 10% (12 total, drop 1 lowest)
  • Quizzes: 60% (14 quizzes, drop 1 lowest)
  • Assignments: 30% (7 assignments)
  • Class engagement: tie breaker

Time Commitment

Preparing for weekly material will demand a significant time commitment, and 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 perhaps 12 to excel. A tentative breakdown of the weekly time is provided above—- please budget 10-12 hours a week for this class.

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 be happy to provide additional problems.

Flex days

To provide reasonable flexibility with deadlines, you are allotted three flex days for the semester, each of which may be used to submit an assignment or a quiz up to 24 hours late (up to 72 hours late if all three flex days are applied all at once). For a team project, applying a flex day uses a flex day from each group member’s allotment. Beyond the use of flex days, quizzes and assignments will not be accepted after the posted due date,unless alternate arrangements have been approved in advance of the deadline. If you have an unusual situation that you forsee impacting your ability to meet a deadline, please let me know as soon as possible so that we can make a plan.

What you can expect from me:

My goal is to create a class that’s similar to algorithms classes at peer institutions. For many of you, this is the first and last algorithm class you’ll take; some of you will go on to software engineering careers; many of you will go at some point through technical interview. For all of these reasons it is important to pack as many topics as possible in the syllabus and expose you to many problems.

The syllabus is packed and you will find the pace and the problems challenging. I often choose problems from the top R1 universities (such as Stanford, MIT, Berkeley, etc). 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, with solutions.

Please don’t hesitate to let me know if you have any significant circumstances that hinder your learning, and we will work together to make an alternate plan.

Key Tips

You will probably find this class to be difficult. What makes it hard is that the material is theoretical and spans many levels of abstraction. Adding to 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. It is important that you know this ahead of time and you start preparing mentally.

Here are some suggestions for doing well in class:

  • Budget your time as suggested above and give yourself plenty of time to read the materials and work on the assignments each week. Plan on 10-12 hours a week, and make a schedule which you follow every week.

  • Be pro-active about things that are not clear; search for resources on the Internet

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

  • Come to office hours, join the study groups and talk to 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!