Homeworks
Unit D
Solutions to Basic Homework
D_Basic: Reductions and NP-Complete
- Instructions: The one and only basic homework for Unit D. Download the .tex file and add your answers to the questions in it. Put your answer right below each question. We’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Tuesday, 5/3, 2022 at 11:30 pm. Submit to GradeScope.
- Late submissions: you may submit “late” up until Friday, 5/6, 2022 at 11:30 pm. (Not 11:59, not midnight!) The penalty for a late submisssion is…. there is no penalty! Note: this is a hard deadline because we’ll release solutions the next morning.
Advanced Homework
- Instructions: Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Tuesday, May 3, 2022 at 11:30 pm. (Not 11:59, not midnight!) Submit to GradeScope.
- Because we’re at the end of term, there is no “early deadline” option for this HW. :-(
Programming Homework
- Instructions: See the homework description PDF file below for complete instructions. You should download the set of starter code, which includes both Python and Java. While each language is different, the algorithm will be the same, so choose the language you are familiar with.
- Homework Instructions - Tiling Dino
- Starter Code:
- Due date: May 3, 11:30pm. Submit to Gradescope.
- Note: Gradescope will only run tests for and grade your first 15 submissions. It’s important to plan your algorithm before coding and write your own test cases.
- To make sure your program compiles and runs on GradeScope, there is a “testing” submission site called Unit D - Programming (Testing Only) that will try your program against the images that we have given you in the Zip file. Make sure your program works here before you submit to the “real” GradeScope assignment with more test-cases that will be available later.
- Only submit your TilingDino and supplement files (if needed). You do not need to submit your test cases or Main file.
Unit C
Solutions to Basic Homeworks
Basic Homework
C1_Basic: Dynamic Programming
- Instructions: The first (of two) basic homeworks for UnitC. Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, April 15, 2022 at {\bf 11:30 pm.} (Not 11:59, not midnight!) Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
C2_Basic: Greedy
- Instructions: The second basic homework for UnitC. Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, April 15, 2022 at {\bf 11:30 pm.} (Not 11:59, not midnight!) Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
Advanced Homework
- Instructions: Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, April 22, 2022 at 11:30 pm. (Not 11:59, not midnight!) Submit to GradeScope.
Programming Homework
- Instructions: See the homework description PDF file below for complete instructions. You should download the set of starter code, which includes both Python and Java. While each language is different, the algorithm will be the same, so choose the language you are familiar with.
- Homework Instructions - Seam Carving
- Starter Code:
- Due date: May 3, 11:30pm. Submit to Gradescope. Submissions with test cases will open Monday, April 11.
- Note: Gradescope will only run tests for and grade your first 20 submissions. It’s important to plan your algorithm before coding and write your own test cases.
- To make sure your program compiles and runs on GradeScope, there is a “testing” submission site called Unit C - Programming (Testing Only) that will try your program against the images that we have given you in the Zip file. This is available Wednesday, April 6, and there is no limit to the submissions. Make sure your program works here before you submit to the “real” GradeScope assignment with more test-cases that will be available later.
- Only submit your SeamCarving and supplement files (if needed). You do not need to submit your test cases or Main file.
Unit B
Solutions to Basic Homeworks
Basic Homework
B1_Basic: BFS and DFS
- Instructions: The first (of two) basic homeworks for UnitB. Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, March 18, 2022 at {\bf 11:30 pm.} (Not 11:59, not midnight!) Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
B2_Basic: DFS, Topological Sort, SCCs, Kruskal’s, Prim’s and Dijkstra’s
- Instructions: The second (of two) basic homeworks for UnitB. Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Note: A update clarifying Problem 2.A was added to these files on 2/14 at 8:00 pm.
- Download this file and modify it.
- You will also need these two image files:
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, March 18, 2022 at {\bf 11:30 pm.} (Not 11:59, not midnight!) Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
Advanced Homework
- Instructions: Download the .tex file and add your answers to the questions in it. Put your answer right below each question. This time we’ve added a \solution{} LaTeX item where you can include your solution, if that helps. (If you don’t use it, put the text Solution at the beginning of each answer.)
- Download this file and modify it.
- You will also need this image files: vulnerable-sets.png
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, April 8, 2022 at {\bf 11:30 pm.} (Not 11:59, not midnight!) Submit to GradeScope.
Programming Homework
- Instructions: See the homework description PDF file below for complete instructions. You should download one of the sets of starter code for your chosen programming languages. While each language is different, the algorithm will be the same, so choose the language you are familiar with.
- Homework Instructions - Supply Chain
- Starter Code:
- Due date: April 15, 11:30pm. Submit to Gradescope. Submissions with test cases will open Fri., April 1. Update: Due Sunday, April 17, 11:30pm. Late submissions with 10pt penalty by Tuesday, April 19, 11:30pm
- Note: Gradescope will only run tests for and grade your first 20 submissions. It’s important to plan your algorithm before coding and write your own test cases.
- To make sure your program compiles and runs on GradeScope, there is a “testing” submission site called Unit B - Programming (Testing Only) that will try your program against one test-file, the one that we have given you in the Zip file. This is available right now and there is no limit to the submissions. Make sure your program works here before you submit to the “real” GradeScope assignment with more test-cases that will be available later.
- Only submit your Supply and supplement files (if needed). You do not need to submit your test cases or Main file.
Unit A
Solutions to Basic Homeworks
Advanced Homework
- Instructions: Download the .tex file and add your answers to the questions in it. Put your answer right below each question with the text Solution at the beginning of each answer.
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, Mar. 4, 11:30pm. Submit to Gradescope.
- If you submit by Feb 21, we will provide feedback by March 1
Programming Homework
- Instructions: See the homework description PDF file below for complete instructions. You should download one of the sets of starter code for your chosen programming languages. While each language is different, the algorithm will be the same, so choose the language you are familiar with.
- Homework Instructions - Choosing Mars Pioneers
- Starter Code:
- Due date: Friday, Mar. 4, 11:30pm. Submit to Gradescope. Submissions will open Wed, Feb 16.
- Note: Gradescope will only run tests for and grade your first 10 submissions. It’s important to plan your algorithm before coding and write your own test cases.
- Only submit your ClosestPair and supplement files (if needed). You do not need to submit your test cases or Main file.
Basic Homework
A3Basic: Quicksort, QuickSelect, Strassen’s, Lower Bound Proof
- Instructions: The third (of three) basic homeworks for Unit A. Download the .tex file and add your answers to the questions in it. Put your answer right below each question with the text Solution at the beginning of each answer.
- Download this file and modify it.
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, February 18, 2022 at 11:30 pm Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
A2Basic: Sorting, Divide and Conquer, Recurrences
- Instructions: The second (of three) basic homeworks for Unit A. Download the .tex file and add your answers to the questions in it. Put your answer right below each question with the text Solution at the beginning of each answer.
- Download this file and modify it. (Minor update 2/5, 1:00 pm)
- Here’s the PDF of this file (so you can look at the questions now if you wish).
- Due date: Friday, February 18, 2022 at 11:30 pm Submit to GradeScope. Note: this is a hard deadline because we’ll release solutions the next morning.
A1Basic: LaTeX Practice (AKA Homework 0)
