## Basic info

**Lecture (A)**: Tu, Thu 10-11:25 (Searles 223, Toma)

**Lecture (B)**: M, We 8-9:25 (Searles 126, Majercik)

**L1:** Fri 11:30 – 12:55 (Searles 126, Toma)

**L2**: Fri 10-11:25 (Searles 126, Majercik)

**Prerequisites**: csci 101 (Intro to CS) and csci 2101 (Data Structures). Generally speaking, a good mathematical background and good QR skills are not required, but are helpful.

**Textbook (required):** Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd Edition, McGraw Hill, New York, 1990. (bugs).

**Class webpage:** *http://courses.bowdoin.edu/computer-science-2200*. This site will contain all class-related material along the semester. The class does not have a Blackboard site.

**Schedule:** For useful links and detailed class schedule, check Syllabus.

## Course overview

Coming up with solutions (algorithms) to problems, proving their correctness and analyzing their efficiency, from various points of view (CPU, IO, bandwidth, best-case, worst-case, etc) are some of the basic questions asked in Computer Science.

This course is an introduction to the design and analysis of algorithms. We talk about analysing the efficiency of algorithms and introduce asymptotic notation and recurrence relations. We discuss fundamental data structures such as (search trees and augmented search trees) priority queues, skip lists and union-find data structures. We introduce major algorithmic problems such as searching, sorting and selection, matrix multiplication, optimization, graph problems, networks, string matching and NP-completeness. We discuss a variety of solutions to these problems, while illustrating techniques such as divide-and-conquer, dynamic programming and greedy.

The class is theoretical and involves no programming.

## Course goals:

- To be able to analyze the asymptotic performance of algorithms using big-oh and big-theta notation
- To be able to compare multiple algorithms for a problem and predict performance
- To be able to argue informally that an algorithm is correct
- To be familiar with the fundamental algorithms and data structures
- To be familiar with the major design paradigms
- To be able to apply these techniques to new problems

## …..and more broadly:

- To get an appreciation of algorithms and an understanding of their importance and impact in Computer Science and beyond
- To improve problem solving skills and power of abstraction
- To develop a database of algorithms and techniques which you’ll use as building blocks to solve new problems

## TAs and study groups

**TAs:** Clara Hunnewell, Dan Navarro, Clara Belitz, Mingo Sanchez,

**Study groups:**

- Sundays 7:30-9:30pm [Clara Belitz]
- Tuesdays 7-9pm [Dan Navarro]
- Thursdays 6-8pm [Mingo Sanchez], 7-9pm [Clara Hunnewell]

All study groups are in Searles 224.

## Labs and Homework

The lab time is dedicated to practice problems, and sometimes to finishing some of the details from lectures. A lab will usually contain a set of problems to be completed in the lab, and a problem set that becomes the homework assignment for the following week. Learning in this class depends crucially on seeing new problems, and we strongly suggest that you spend the lab time working on the suggested problems, rather than starting the assignment.

The assignment is considered an opportunity for learning and completing the assignment is a learning **process**. You are not expected to sit down for a few hours and solve everything in a breath! Instead, you are expected to view it as a process: read the problems, understand what they are asking, come up with initial solutions, figure out whether they work or not, fix them, repeat. The whole process is supposed to be interactive between you, the group of people you collaborate with, the TAs and study group leaders, and the instructors.

The course relies heavily on group work and peer instruction, so it is crucial that you attend all classes and all labs. There is a lot of research that shows the benefits of peer instructions compared to standard lecturing. The process of explaining an argument is beneficial for everybody involved. You’ll work in groups in class, during labs, and in the study groups.

## Homeworks, Exams and Grading policy

**Homework:** The weekly lab will contain some problems to be solved in the lab, and a set that constitues the homework for the subsequent week. The homeworks will generally be due a week later (unless specified otherwise). Late assignments are not accepted (except in case of medical reasons).

**Exams:** There will be two exams, one half-way through the semester [see syllabus], and the second one during the final exam period [check precise date in posted in polaris]. Tentatively, the first exam will be take-home, the second exam will be in-class; this is just tentative, and may change. The exams will be open book and open notes, and non-cumulative (to the extent possible).

**Homework collaboration policy:** You are encouraged to work on problems in a group. You will find that you will gain a better understanding of the material by discussing the problems with your partners. However, you must write up the solutions **individually**. Limit your collaborators to three or less, and list the names of the collaborators on the homework.

**Grading policy:** The final grade is determined as follows:

- Homework assignments (40%).
- 2 exams (2 x 30 = 60%).
- Class participation (5%)

## Topics

The following general topics will be covered, which correspond to chapters in your textbook and will be studied approximately in the same order as they appear in the textbook. For a precise schedule, check the syllabus.

- Mathematical foundation (growth of functions, summations, recurrences, induction)
- Sorting algorithms (insertion sort, selection sort, mergesort, quicksort, heapsort, sorting lower bounds, bucket sort, radix sort)
- Searching and data structures (binary search trees, red-black trees, augmented search trees, skip lists)
- Priority queues (binary heap)
- Selection
- Paradigms (divide-and-conquer, greedy, dynamic programming)
- Graph Algorithms (traversal, minimum spanning trees, shortest paths)
- [Time-permitting: Network algorithms (network flow) and String matching algorithms]
- NP-completeness (quick intro)

## Academic Integrity

You are expected to follow Bowdoin’s academic honor code. Collaboration on homeworks is encouraged, however you are responsible to write the solutions on your own, and list the names of all your collaborators. You may not glance over someone else’s written solution, and you may not share your problems sets and exams with anybody else, this term or in the future. Any violation will be reported and treated according to Bowdoin’s academic integrity guidelines.