Algorithms, Fall 2023

Syllabus

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

Class time: TR 11:40-1:05, 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 we’ll see 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 (justify correctness) or incorrect (come up with counter-examples)
   3. Analyze their theoretical complexity and compare them
   4. Consider the question: Can the solution be improved?

Schedule at a glance

Week 1, 2, 3	Introduction and review (bubble sort, insertion sort, selection sort, best case and worst cases analysis). Analysis tools (asymptotic notation, summations, recurrences).
Week 4, 5, 6	Efficient sorting (mergesort, heapsort, quicksort, randomized quicksort). Sorting lower bound, bucket sort and counting sort. Selection with quick-select) and in O(n) worst-case.
Week 7, 8, 9, 10	Techniques (divide-and-conquer, dynamic programming and greedy).
Week 11, 12, 13, 14, 15	Graphs basics, shortest paths on DAGs, Dijkstra’s and Bellman-Ford SSSP algorithms, and minimum spanning trees with Kruskal’s and Prim’s algorithms.

Read 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 class. This will make the classes more pleasant and effective and will allow time for class work.

The labs

Every week we have a designated lab period in which you’ll work on a set of activities focused on the topics discussed that week. The lab problems are meant to be solved in class, during the designated lab time, working with your group. Myself and the LAs will be around to work with you, facilitate discussions and answer questions.

Labs are not graded and their goal is to help you learn. It is important that you strive to work through all problems, formulate questions, check your notes, discuss with your group, the LAs and the instructor, and get your questions answered. We will ocasionally go over solutions to some lab problems as a class and if you find that useful (or not) be sure to let me know how you feel so that we can adjust.

Overall you’ll probably find that most of your learning occurs in the lab while working with your peers!

Assignments

There will be 8-12 assignments this semester, roughly one assignment per week, which will be released in Gradescope — watch Slack for the announcement.

The assignments consist of new problems for which you’ll have to come up with efficient solutions on your own. The assignments will generally be hard and will provide opportunities to learn at a deeper level, and will work towards the learning goal of “develop solutions to new problems”.

We expect everyone to do well on the homework, and to take the time to write your work carefully. 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.

Assignment partner policy: You may work with one partner (see course policies for details on what this means). One member of the team should submit the assignment and should add the other member to the “team” so that (s)he can get the credit.

Assignment honor code:

• Level 1: Assignments are at collaboration-level 1; that is, verbal collaboration without solution sharing (check course policies for details on what this means).

• Use the internet to learn, but don’t cheat: There are lots of resources online, such as lecture notes, animations, visualizations, practice problems, video recordings, which you are encouraged to explore to help you understand the material. However, you must be careful not to search the internet (and that includes ChatGPT) for the homework problems. Searching for the assignment problems on the internet violates academic honesty for this class.

Work and Grading Policy

• Quizzes: 10% There will be 5 quizzes in the first half of the semester. Expect them to be short and focused on the specific topic discussed that week. They will be released in Canvas and you’ll take them remotely from your room. They are self-graded. They are all weighed equally (although the number of questions in each will be different).

• Assignments: 40%

• Exams: 50% 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. The exams weigh 15%, 15% and 20%, respectively.

• 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 in order to achieve the learning goals. The actual time will vary from week to week as some topics (esp towards the middle of the semester) will be harder and may take more hours, and also based on your background and interests.

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 improve your analytical and abstraction abilities 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 all work well together. Open collaboration in the lab is highly encouraged. All 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. 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 likely find this class to be difficult and very different than 2101. The material is theoretical and spans many levels of abstractions. Furthermore 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.

2101 vs 2200: Working on an algorithms assignment will seem easier than working on a programming assignment in Data Structures (remember debugging).

• 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 is efficient and justifying that it is correct. That’s the beauty of theory.

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). BUT: don’t search for the assignment problems (because that violates the honor code and you won’t learn anythingmuch).

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