Course overview
Goal of the class is to learn algorithmic thinking through gaining familiarity with some of the most important algorithms and the implementational challenges related to them. The course will involve implementing algorithms and a lot of hands on work. The goal is to make you comfortable with the theory and to know how to implement the algorithms. The language used will be python.
General information
Instructor: Sylvester Eriksson-Bique, 6164 Math Sciences Building.
Office Hours: Monday 5-6pm , Wed 12:00pm–1:00pm 6164 Math Sciences Building.
Lecture times: MWF 4-5pm Geology 4645
TA:
- Xuchen Han, discussion section Tuesday 4-5pm in PIC lab. Office hours on CCLE.
HW: Available on CCLE, Piazza.
Exams: One in class midterm: Fri Nov 2nd. Three-hour final: Monday, December 13th, 8am-11am Location TBD, and available on myUCLA from 11/26 onwards, and will be announced on CCLE.
Bring student ID to both midterm and the final.
No calculators, notes, or books will be permitted in any exam.
Grading
The course will consist of
- Group work culminating in a collaborative project: 20 % + potential for 5 % extra credit
- Participation in discussion sections: 5 %
- Online participation: up to 5 % extra credit, depending on activity. 1% for each upvoted question, up to 3, and 1 % for at least 5 thoughtful responses, and 2% if more than 10.
- Homework: 15 %
- First midtem: 25 %
- Final: 35 %
Course grade assignment
- Generally a C in this class will require completing the assignments sincerely, and demonstrating that you learned the core concepts from this class.
- A grade B will mean roughly that you absorbed most of the material and tentatively will require a 80% score.
- A grade A will result from a very good performance, and tentatively is given with 90% or over.
- No curving will be used, but I may adjust the percentages lower so that the scores match the skills. Everyone who does well, can get a good grade, even an A.
PIC Lab and Anaconda
We will use the PIC lab for all recitations and some lectures (with due notice). You should soon receive an email giving you accounts, and you should make them. This will also give you access
to the collaborative side of the PIC laboratory, in the MathSci building 2000. Feel free to work there together on the group projects. The lab can be found by taking either the stairs or the elevator to the second floor.
It may be a bit confusing to find it, but once you get to the second floor, it is hard to miss it.
The HW and assignments should be Python 2 compatible.
All the homework will be returned as Jupyter notebooks. And this will also be the format for the Course projects. The easiest way to use it, and to code python, is to install
a distribution of Anaconda on your computer. Or, if you so choose, you can do all your HW in a sitting at the PIC lab, directly editing the HW notebook file.
Policies
- University policy requires participation in the final.
- Only exceptions can excuse from midterm, in which case grade based on replacement exam.
- HW will always be announced on CCLE, posted here and there.
- No late HW, two lowest HW dropped
- HW due online usually by Monday night following the posting, uploaded online. Can collaborate but code not identical!
- HW will be given as a Jupyter notebook, where the student can add their answers.
- HW returned in online on CCLE
- Consists of programming, T/F questions, explanations and analysis problems.
- Each problem on HW graded for completeness, correctness, for code running, returning correct answers and level of understanding.
- Commented code is generally required for a perfect score. Grader may
deduct points for answers that are hard to understand, or whose correctness is too time consuming to verify. - Bring ID to exam. No notes or books allowed.
- There will be no make up exams.
- Participation in discussion sections is necessary for full credit. You receive full credit for attending 7/9 of all the sessions.
Group project policies: Suggested!
- Groups due Oct 10th.
- Problem phase and decision due Oct 26th.
- Designing algorithm phase and subdividing problem due on Nov 5th.
- Programming phase due Nov 26th.
- Testing design and implementation due on Nov 28th.
- Final report and writing up due Dec 7th.
- Groups of 4 students desired, but may be 5 or 3.
- Group project written as a Juypiter notebook file collaboratively
- Final will ask about a part of your project!! Everyone must have ownership and complete part of the project
- Graded together as a group.
- Extra 5 % granted to any group with an excellent project. May be a hard problem, a beautiful solution a thoughtful analysis, good analysis and comparison of approaches, efficient algorithm… If all succeed well,
everyone will get extra credit. - In the lectures, we will do an example project together, or at least discuss most parts in detail with a sample problem.
- Sample problems will be posted online.
- Partially completed projects may be graded, but will not receive full credit.
- Groups should not be changed after being formed. Discuss with instructor/TA if issues arise.
- Work together!!
Jypiter:
This course will use jypiter notebooks for the HW and the final project. These are easy to use files
that integrate both executable python code, images, and text with minimal formatting (titles, bullet points…).
It enables to have code side-by-side with its explanation and will help the TA evaluate your HW. The environment is easy to use,
and quick to learn.
You can access all the relevant information on http://jupyter.org/. The easiest way to use it is installing Anaconda
https://www.anaconda.com/download/. This is a simple cross-platform environment for many tools, including Jupyter notebooks and Jupyter labs
for editing, running, and managing python code/Jupyter notebooks involving python code. It also has Ipython which allows for graphing material, as well as installs a python distribution so you
can run code just by writing `python filename.py’, or open a python terminal by writing `python’ in your terminal, and then it will interpret line-by-line your python code. I will introduce these tools to you in our first class on Thursday.
Syllabus:
Tentative course schedule
Lecture | Date | Section | Topic |
1 | Friday Sept 29th | 1,5.1,5.2 | Formulating algorithmic problems: Sorting and insertion sort |
2 | Mon Oct Oct 1st | 1,2,5.1,5.2 | Comparing algorithms: efficiency and big O, Examples of complexity classes |
1 | Tuesday Sept 28th | 5.1,5.2 | PIC LAB!!! Introduction Python and PIC lab. |
4 | Wed Oct 3rd | 5.1,5.2 | Divide and conquer: Complexity, Binary search and Merge Sort |
NA | Friday Oct 5th | NA | Deadline for groups; TA Discussion section, in PIC LAB |
5 | Mon Oct 8th | 5.6 | Divide and conquer: FFT and Matrix multiplication |
6 | Wed Oct 10th | 5.6 | FFT |
7 | Fri Oct 12th | 3.1-3.4 | Graphs: DFS and BFS, Bipartite graphs |
8 | Mon Oct 15th | 3.1-3.4, 4.4,4.5, 2.5 | Graphs: Dijkstra, data structures |
9 | Wed Oct 17th | 4.4,4.5, 2.5 | Dijkstra and Minimum spanning trees, data structures |
10 | Fri Oct 19th | 6.1-6.2 | Problem phase due! Dynamic programming: Interval scheduling |
11 | Mon Oct 22nd | 6.4 | Dynamic programming: Weighted interval scheduling and Knapsack and subset sum |
12 | Wed Oct 24th | 6.6 | Dynamic programming: Sequence alignment |
13 | Fri Oct 26th | 4.1 | Greedy algorithm: Interval scheduling |
14 | Mon Oct 29th | Review and discussion | |
15 | Wed Oct 31st | 4.8 | Greedy algorithm: Huffman codes |
16 | Fri Nov 2nd | Midterm: Up to Lecture 13 | |
17 | Mon Nov 5th | Data structure: Basic operations, Heap, Binary Search Tree | |
18 | Wed Nov 7th | 2.5, and elsewhere | Data structure: Basic operations, Union find |
19 | Fri Nov 9th | Complexity lower bounds: Sorting, | |
20 | Mon Nov 12th | NA | Veterans day observance |
21 | Wed Nov 14th | Papadimitriu | Python code due!! Symbol tables and priority queues |
22 | Fri Nov 16th | Papadimitriu | Complexity lower bounds: Sorting, Equivalence of problems, reductions, P and NP |
23 | Mon Nov 19th | Sedgewick | Hash tables and hash functions |
24 | Design and implement test! Wed Nov 21st | Sedgewick | Hash tables and hash functions |
25 | Fri Nov 23rd | Thanksgiving | |
26 | Mon Nov 26th | 7 | Graph algorithms: Network flows |
27 | Wed Nov 28th | 7 | Graph algorithms: Network flows |
28 | Fri Nov 30th | Sedgewick | Amortized complexity: Union find |
29 | Mon Dec 3rd | Sedgewick | Amortized complexity: Union find |
30 | Wed Dec 5th | Sedgewick | Additional topic: Randomization and Quicksort |
31 | Fri Dec 7th | Sedgewick | Additional topic: Randomization and Quicksort Projects due on Sunday!! Last class: review |
FINAL | Thur Dec 13th | Cumulative | 8am-11am Location TBD |
Notice about academic integrity
From the office of the Dean of Students:
“With its status as a world-class research institution, it is critical that the University uphold the highest
standards of integrity both inside and outside the classroom. As a student and member of the UCLA
community, you are expected to demonstrate integrity in all of your academic endeavors. Accordingly,
when accusations of academic dishonesty occur, The Office of the Dean of Students is charged with
investigating and adjudicating suspected violations. Academic dishonesty includes, but is not limited
to, cheating, fabrication, plagiarism, multiple submissions or facilitating academic misconduct.”
Students are expected to be aware of the University policy on academic integrity in the UCLA Student
Conduct Code:
http://www.deanofstudents.ucla.edu/Portals/16/Documents/UCLACodeOfConduct_Rev030416.pdf
Please note the sections on (1) cheating, (2) plagiarism, and (3) unauthorized study aids.
Violation of course policy involving plagiarism, cheating, or possession of course materials during
exams will be referred to the Dean of Students, who will be encouraged to take strong action. Do not
cheat! The penalties can be very harsh. Do not believe it if you hear that “everyone does it.” You
generally do not hear about the punishments because they are kept confidential. If you are found
responsible by the Dean of Students for violating course policy, cheating on any course materials, or
giving or receiving unauthorized help, a zero will be assigned for the entire assignment. No exceptions
will be made! Past examples of penalties also include loss of an entire term of credit and suspension for
several terms. If you plan to apply to graduate or professional school, such a negative mark on your
record may be a major obstacle to admission.
No cell phones are allowed during exams. They must be left in your bag and turned off, or submitted to
the designated TA/proctor. Students may not use a cell phone as a clock to keep time, nor as a
calculator. No hats are allowed in the testing room; they must be left in your bag.
Notice about sexual harassment, discrimination, and assault
Title IX prohibits gender discrimination, including sexual harassment, domestic and dating violence,
sexual assault, and stalking. Students who have experienced sexual harassment or sexual violence can
receive confidential support and advocacy from a CARE advocate:
The CARE Advocacy Office for Sexual and Gender-Based Violence
1st Floor, Wooden Center West
CAREadvocate@caps.ucla.edu
(310) 206-2465
You can also report sexual violence or sexual harassment directly to the University’s Title IX
Coordinator:
Kathleen Salvaty
2241 Murphy Hall
titleix@conet.ucla.edu
(310) 206-3417
CAE brochure and Counceling
My goal is to foster an inclusive, supportive and encouraging enviroment for you to learn. Many of us suffer from various degrees
of learning difficulties, exam stress etc, or difficulties in our private lives. Please be aware that the university has many resources to help with challenges you might face
and that I as an instructor will do my best to assist and accomodate different learners. Please do not be afraid to reach out to a councelor,
me or your TA for contact information to various services. Also, please review the attached links for more resources.