Math 182 – Algorithms – Fall 2018

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.

https://www.counseling.ucla.edu/

https://www.cae.ucla.edu/learning-disabilities-brochure