Course Syllabus

\documentclass[11pt,letterpaper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{fancyhdr}
\usepackage{xcolor}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{tabularx}
\usepackage{titlesec}
\usepackage{parskip}

\pagestyle{fancy}
\fancyhf{}
\lhead{\textbf{CS 261}}
\chead{\textbf{Fall 2025}}
\rhead{\textbf{Course Syllabus}}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.8pt}

\definecolor{sectionblue}{RGB}{0,51,102}
\titleformat{\section}{\large\bfseries\color{sectionblue}}{}{0em}{}[\vspace{-4pt}\textcolor{sectionblue}{\hrule height 0.6pt}\vspace{2pt}]

\setlength{\parindent}{0pt}

\begin{document}

\begin{center}
  {\LARGE\bfseries\color{sectionblue} CS 261: Data Structures and Algorithms}\\[8pt]
  {\large Fall 2025 --- University of California, Berkeley}\\[4pt]
  {\large Lecture: Mon/Wed/Fri 10:00--10:50 AM, Wheeler Hall 150}
\end{center}

\vspace{8pt}

\section{Instructor Information}

\begin{tabularx}{\textwidth}{@{}lXlX@{}}
  \textbf{Instructor:} & Prof.\ Amir Hassani & \textbf{Email:} & \href{mailto:[email protected]}{[email protected]} \\
  \textbf{Office:} & Soda Hall 785 & \textbf{Phone:} & (510) 642-5100 \\
  \textbf{Office Hours:} & Mon 2--4 PM, Wed 1--2 PM & & \\
\end{tabularx}

\vspace{4pt}

\textbf{Teaching Assistants:}
\begin{itemize}[nosep]
  \item \textbf{Lisa Nakamura} --- \href{mailto:[email protected]}{[email protected]}, Office Hours: Tue 3--5 PM (Soda 341)
  \item \textbf{Carlos Mendez} --- \href{mailto:[email protected]}{[email protected]}, Office Hours: Thu 1--3 PM (Soda 341)
  \item \textbf{Priya Sharma} --- \href{mailto:[email protected]}{[email protected]}, Office Hours: Fri 2--4 PM (Soda 341)
\end{itemize}

\section{Course Description}

This course provides a comprehensive study of the design, analysis, and implementation of data structures and algorithms. Topics include asymptotic analysis, divide-and-conquer algorithms, sorting and searching, graph algorithms, dynamic programming, greedy algorithms, amortized analysis, balanced search trees, hash tables, and NP-completeness. Emphasis is placed on rigorous mathematical analysis alongside practical implementation skills.

\textbf{Prerequisites:} CS 161 (Introduction to Computer Science) and MATH 55 (Discrete Mathematics), or equivalents with instructor consent.

\textbf{Textbook:} Cormen, Leiserson, Rivest, and Stein. \textit{Introduction to Algorithms}, 4th Edition. MIT Press, 2022. (Required)

\textbf{Supplementary:} Kleinberg and Tardos. \textit{Algorithm Design}. Pearson, 2006. (Recommended)

\section{Learning Objectives}

Upon successful completion of this course, students will be able to:
\begin{enumerate}[nosep]
  \item Analyze the time and space complexity of algorithms using asymptotic notation.
  \item Design algorithms using fundamental paradigms: divide and conquer, dynamic programming, and greedy methods.
  \item Implement and analyze core data structures including balanced BSTs, heaps, hash tables, and graphs.
  \item Prove correctness of algorithms using loop invariants, induction, and structural arguments.
  \item Recognize NP-complete problems and apply reduction techniques.
\end{enumerate}

\section{Grading Policy}

\begin{tabular}{@{}lr@{}}
  \toprule
  \textbf{Component} & \textbf{Weight} \\
  \midrule
  Homework Assignments (8 total, drop lowest) & 25\% \\
  Programming Projects (3 total) & 15\% \\
  Midterm Exam 1 (Oct 8, in class) & 15\% \\
  Midterm Exam 2 (Nov 12, in class) & 15\% \\
  Final Exam (Dec 15, 8:00--11:00 AM) & 25\% \\
  Participation and Discussion Sections & 5\% \\
  \midrule
  \textbf{Total} & \textbf{100\%} \\
  \bottomrule
\end{tabular}

\vspace{6pt}

\textbf{Letter Grade Cutoffs:} A+: 97+, A: 93--96, A$-$: 90--92, B+: 87--89, B: 83--86, B$-$: 80--82, C+: 77--79, C: 73--76, C$-$: 70--72, D: 60--69, F: below 60. Cutoffs may be adjusted downward (curved) at the instructor's discretion.

\section{Course Schedule}

\begin{longtable}{@{}clll@{}}
\toprule
\textbf{Week} & \textbf{Dates} & \textbf{Topics} & \textbf{Reading / Due} \\
\midrule
\endfirsthead
\toprule
\textbf{Week} & \textbf{Dates} & \textbf{Topics} & \textbf{Reading / Due} \\
\midrule
\endhead
1 & Aug 25--29 & Course overview; Asymptotic analysis & CLRS Ch.\ 1--3 \\
2 & Sep 1--5 & Recurrences; Master theorem & CLRS Ch.\ 4; HW 1 out \\
3 & Sep 8--12 & Divide and conquer: merge sort, quicksort & CLRS Ch.\ 7--9; HW 1 due \\
4 & Sep 15--19 & Heaps and priority queues & CLRS Ch.\ 6; HW 2 out \\
5 & Sep 22--26 & Binary search trees; Red-black trees & CLRS Ch.\ 12--13; HW 2 due \\
6 & Sep 29--Oct 3 & Hash tables; Amortized analysis & CLRS Ch.\ 11, 17; Proj 1 out \\
7 & Oct 6--10 & \textbf{Midterm 1 (Oct 8)}; Graph representations & CLRS Ch.\ 22; HW 3 due \\
8 & Oct 13--17 & BFS, DFS, topological sort & CLRS Ch.\ 22; Proj 1 due \\
9 & Oct 20--24 & Shortest paths: Dijkstra, Bellman--Ford & CLRS Ch.\ 24; HW 4 out \\
10 & Oct 27--31 & Minimum spanning trees: Kruskal, Prim & CLRS Ch.\ 23; HW 4 due \\
11 & Nov 3--7 & Dynamic programming I & CLRS Ch.\ 15; HW 5 out; Proj 2 out \\
12 & Nov 10--14 & \textbf{Midterm 2 (Nov 12)}; DP II & CLRS Ch.\ 15; HW 5 due \\
13 & Nov 17--21 & Greedy algorithms & CLRS Ch.\ 16; Proj 2 due \\
14 & Nov 24--25 & Network flow & CLRS Ch.\ 26; HW 6 out \\
  & Nov 26--28 & \textit{Thanksgiving Break --- No Class} & \\
15 & Dec 1--5 & NP-completeness; Reductions & CLRS Ch.\ 34; HW 6 due; Proj 3 out \\
16 & Dec 8--10 & Approximation algorithms; Review & CLRS Ch.\ 35; Proj 3 due \\
  & Dec 15 & \textbf{Final Exam (8:00--11:00 AM)} & Comprehensive \\
\bottomrule
\end{longtable}

\section{Policies}

\subsection*{Late Submissions}

Homework and projects are due at 11:59 PM on the specified date via Gradescope. Each student receives \textbf{5 late days} for the semester, usable across homework and projects (max 2 per assignment). After late days are exhausted, late submissions receive a 20\% penalty per day.

\subsection*{Collaboration Policy}

You may discuss homework problems with classmates at a high level, but all written solutions must be your own. You must list all collaborators on your submission. Programming projects must be completed individually unless explicitly designated as group work. Sharing code is prohibited.

\subsection*{Academic Integrity}

All students are expected to adhere to the UC Berkeley Honor Code. Violations---including plagiarism, unauthorized collaboration, and use of unauthorized materials during exams---will be reported to the Center for Student Conduct and may result in a failing grade for the course. If you are uncertain about what constitutes a violation, ask the instructor before acting.

\subsection*{Accommodations}

Students with disabilities who need academic accommodations should contact the Disabled Students' Program (DSP) at \href{https://dsp.berkeley.edu}{dsp.berkeley.edu} and provide their accommodation letters to the instructor within the first two weeks of the semester.

\subsection*{Communication}

All course announcements will be posted on the course Ed Discussion board. Students are expected to check Ed regularly. For private matters, email the instructor with the subject line prefix \texttt{[CS261]}.

\section{Resources}

\begin{itemize}[nosep]
  \item \textbf{Course Website:} \href{https://cs261.berkeley.edu}{cs261.berkeley.edu}
  \item \textbf{Ed Discussion:} Linked from course website (enrollment via bCourses)
  \item \textbf{Gradescope:} Entry code \texttt{XK7P2R}
  \item \textbf{Tutoring:} HKN and UPE tutoring available in Cory and Soda Halls
\end{itemize}

\end{document}