CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

ˆ Homework solutions should be neatly written or typed and turned in through Gradescope
by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be
able to look at your scanned work before submitting it. Please ensure that your submission
is legible (neatly written and not too faint) or your homework may not be graded.

ˆ Students may consult their textbook, class notes, lecture slides, instructors, TAs, and tutors
when they need help with homework. Students should not look for answers to homework
problems in other texts or sources, including the internet. Only post about graded homework
questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what
the question is asking you to do. Other questions are best addressed in office hours.

ˆ Your assignments in this class will be evaluated not only on the correctness of your answers,
but on your ability to present your ideas clearly and logically. You should always explain
how you arrived at your conclusions, using mathematically sound reasoning. Whether you
use formal proof techniques or write a more informal argument for why something is true,
your answers should always be well-supported. Your goal should be to convince the reader
that your results and methods are sound.

ˆ For questions that require pseudocode, you can follow the same format as the textbook, or
you can write pseudocode in your own style, as long as you specify what your notation means.
For example, are you using “=” to mean assignment or to check equality? You are welcome
to use any algorithm from class as a subroutine in your pseudocode.

ˆ Students can work in a group of 1-4. Each group should submit only one homework.

There are 4, questions for a total of 50, points.

1. (10 points) State True or False:

(a) (2 points) 2 · (3n ) ∈ Θ(3 · (2n ))
False. The constants 2 and 3 don’t change order. 3n /2n = (1.5)n which goes to infinity as n gets
large. So 2 ∗ 3n ∈ ω(32n ), and they are not the same order.
(b) (2 points) (n6 + 2n + 1)2 ∈ Ω((3n3 + 4n2 )4 )
True. We don’t need to compute ratios exactly. For each expression, the highest degree part, which
determines the order, is something times n12 . So they have the same order.
(c) (2 points) log n ∈ Ω((log n) + n)
False. Right side grows faster than the left side, so can’t be a lower bound.
(d) (2 points) n log n + n ∈ O(n log n)
True. A sum of a fixed number of functions has the same order as its maximum term, in this case,
n log n.
(e) (2 points) log(n10 ) ∈ Θ(log(n))
True. log(n10 ) = 10 log n ∈ Θ(log n))
Pn k k+1
(f) (2 points) i=1 i ∈ Θ(n )
True. We don’t need to give an exact expression. The largest term in the sum is nk and there are
n terms, so the sum is upper bounded by nk+1 , showing it is O(nk+1 ). To see the other direction,
we can’t use the smallest term, because that is just 1, but we can use the middle term: i = n/2 and
all n/2 greater terms. Each of those is at least (n/2)k = nk /2k and there are n/2 of them. So the
sum is at least nk+1 /2k+1 which is Ω(nk+1 ) for any fixed k.
(g) (2 points) (log(n))log(n) ∈ O(n/ log(n))
False. This one is a bit tricky. The left is an exponential, but an exponential of a log, which are
inverses of each other. For any fixed b, blog n is a polynomial. But as b increases, the degree of that

1 of 6
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

polynomial grows, and we are comparing on the right to a sub-linear function. So we could argue:
For n ≥ 16, log n ≥ 4, So (log n)log n > 4log n = 2log n 2log n = n ∗ n = n2 ∈ ω(n/ log n).
(h) (2 points) n! ∈ O(2n )
False. If we look at the ratio, n!/2n = 1/2 ∗ 2/2 ∗ 3/2 ∗ 4/2 ∗ ...n/2. All but the first threee terms
are ≥ 2. So the ratio is at least 3/4(2n−3 ) = 3/322n which goes to infinity quickly as n increases.
2. (10 points) The Fibonacci numbers F0 , F1 , F2 , ..., are defined by the following relationship

F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2

(a) (5 points) Use induction to prove that Fn ≥ 20.5n for n ≥ 6.

Show for n = 6 and n = 7. Suppose true up to n.
 
Fn+1 = Fn + Fn−1 ≥ 20.5(n−1) + 20.5n = 20.5n √12 + 1 ≥ 20.5(n+1)
(b) (5 points) What is the largest c you can find for which Fn = Ω(2cn )? Explain your answer.
The largest c should satisfy

2c(n−1) + 2c(n) = 2c(n+1)

2cn−c + 2cn = 2cn+c
2−c + 1 = 2c
√
1+ 5
Set 2c = x : 1 + x < x2 → x = 2 gives
√
c ≥ log2 ( 5 + 1) − 1

3. (10 points) Given a directed graph G = (V, E) and two vertices x and y, give an algorithm to find
whether x and y ate connected. Your algorithm should return one of the following options.
a. There is no path between x and y.
b. There is a path connecting x to y, but no path connecting y to x. In this case return the path
connecting x to y.
c. There is a path connecting y to x, but no path connecting x to y. In this case return the path
connecting y to x.
d. There is a path connecting x to y and vice-versa. In this case return both the paths.
Rubric: correct algorithm and pseudocode [5], proof of correctness [3], running time analysis [2].
Algorithm Description
Run explore(G,x) that is start DFS exploration at x maintaining a parent pointer for every node reached.
If explore(G,x) reaches y, return the path connecting x to y using the parent pointer. Otherwise, return
no path from x to y.
Next run explore(G,y) that is start DFS exploration at y maintaining a parent pointer for every node
reached. If explore(G,y) reaches x, return the path connecting y to x using the parent pointer. Otherwise,
return no path from y to x.
Pseudocode:
Initialize an array of pointers parent[] of size |V |. The ‘list.add(L, i)’ function adds a new item i to the
beginning of a linked list L. The visited[] array is the same as used in Explore() procedure explained
in the slides.
procedure Path(src, dest)
path = [] # Denotes an empty linked list
curr = dest
do

2 of 6
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

path = list.add(path, curr)

curr = parent[curr]
until (curr != src)
path = list.add(path, curr)
return path # Returns the path as a linked list

procedure ModifiedExplore(G = (V, E), v, prev, src, dest)

parent[v] = prev # Maintains a pointer to the parent vertex in the exploration tree
visited[v] = true
if (v == dest):
return Path(src, dest)
for (each edge (v, u) ∈ E):
if (not visited[u]):
ModifiedExplore(G, u, v, src, dest)

procedure ModifiedExploreWrapper(G = (V, E), x, y)

P athXY = ModifiedExplore(G, x, null, x, y) # Assume prev = null as we begin exploration at vertex x
P athY X = ModifiedExplore(G, y, null, y, x)
if (P athXY is null and P athY X is null):
print “There is no path between x and y.”
else if (P athXY is not null and P athY X is null):
print “There is a path connecting x to y, but no path connecting y to x.”
print P athXY
else if (P athXY is null and P athY X is not null):
print “There is a path connecting y to x, but no path connecting x to y.”
print P athY X
else
print “There is a path connecting x to y and vice versa.”
print P athXY
print P athY X

Proof of correctness: This follows from the correctness of the Explore() function taught in the class.
ModifiedExplore() maintains a parent pointer for each vertex that is visited for the first time. Correctness
of Path() comes from the fact that the path is added to the linked list in reverse order of traversal, starting
from y and ending at x when searching for a path from x to y, and hence traversal of the list returned
by Path() will give a valid path from x to y if such a path exists.
Running time analysis: ModifiedExploreWrapper() essentially does two runs of the Explore() func-
tion, which has a running time of O(|V | + |E|). The Path function is run once if a valid path from x
to y is found, and takes O(|V |) time in the worst case. Hence, the final running time of ModifiedEx-
ploreWrapper scales as O(|V | + |E|) + O(|V |) = O(|V | + |E|).
4. (20 points) Each undergraduate student at UCSD needs to take a certain set of courses to graduate.
Each course may have some other courses as prerequisites.

3 of 6
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

(a) (10 points) Design an algorithm that given the set of required courses and the prerequisite informa-
tion either finds a schedule so that a student can graduate in 4 years, or outputs no such schedule
exists. You are provided with an algorithm for topological sorting, and your algorithm should use
that as a subroutine.
Rubric: correct algorithm and pseudocode [5], proof of correctness [3], running time analysis [2].
Algorithm Description
Initialize an array named year with year[i] = ∞ for i = 1, 2, .., |V | (here, |V | = number of required
courses).
Visit vertices in topological sorted order.
While visiting a vertex v, set year[v] = maxu:(u,v)is an edge year[u] + 1
If year[v] > 4 for any vertex return schedule not possible, otherwise return subject v taken in
year[v]
Pseudocode:
Initialize an array adjList of linked lists that holds the adjacency list used to represent the courses
and their pre-requisites as a graph, such that adjList[i]=[], an empty linked list for i = 1, 2, .., |V |.
For a course c, adjList[c] contains the list of courses that can be taken after taking course c. We
also assume schedule to be a HashMap with key-value pairs of (course -> [pre-requisite list]). Like
above, the ‘list.add(L, i)’ function adds a new item i to the beginning of a linked list L.
procedure ConstructGraph(schedule)
Initialize adjList
for (course, prerequisites) ∈ schedule:
for (prerequisite ∈ prerequisites):
adjList[prerequisite] = list.add(adjList[prerequisite], course)
return adjList

procedure FindGraduationCourseSchedule(schedule)
G = ConstructGraph(schedule)
sortedList = TopologicalSort(G)
for (vertex v in sortedList):
prerequisites = schedule[v]
if (prequisites is empty):
year[v] = 1
else
year[v] = maxu:(u,v)∈E year[u] + 1 # Can use schedule to optimize running time within the
“max” operation
for (vertex v in sortedList):
if (year[v] > 4): # If using quarters, this would be 12
return “Schedule not possible”
for (vertex v in sortedList):
print “Subject v taken in Year year[v]” # If using quarters, replace “Year” with “Quarter” or
something equivalent
return “This is the schedule of courses needed to graduate in 4 years”

Proof of correctness: Correctness follows from the correctness of topological sorted order. While
visiting vertex v, all the prerequisites needed to take v must appear before v and has an incoming
edge to v. The algorithm considers years in which these prerequisites are taken, the max operation
ensures the year in which all prerequisites are completed. The course v is taken in the following
year.

4 of 6
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

Running time: ConstructGraph() takes O(|V |) time to initialize the adjacency list, and O(|E|)
to add the edges to it, so overall it takes O(|E|) in the worst case. Topological sort runs in
O(|V |+|E|) time, in the worst case. The first for loop iterates over all edges of the constructed graph
G = (V, E) (due to the max operation), and this takes O(|V | + |E|) time. The remaining for loops
in FindGraduationCourseSchedule() takes O(|V |) time as it visits all vertices in the constructed
graph G. Hence, the overall running time of FindGraduationCourseSchedule() is O(|E|) + O(|V | +
|E|) + O(|V | + |E|) + O(|V |) + O(|V |) = O(|V | + |E|).
(b) (10 points) A CSE 101 student has suggested the following solution for the above problem. Rep-
resent the prerequisite structure using a directed graph G = (V, E) so that vertices represent the
courses and if a course y ∈ V has a course x ∈ V as prerequisite then there exists a directed edge
from x to y in E. Find all the zero in-degree vertices in this graph and take those courses in the
first quarter. Remove all these vertices with zero in-degree along with all the outgoing edges from
them. Find all the zero in-degree vertices in this modified graph, and take those courses in the
second quarter. Remove these vertices and all of its out-going edges. Keep repeating the above to
find the schedule for all 12 quarters.
Give an implementation of the above algorithm that runs in O(|V | + |E|) time. What is the space
complexity of the implementation?
Rubric: correct implementation [5], proof of correctness [2], space complexity [3].
Implementation:
Maintain an array Index where Index[i] maintains a doubly linked list to explore all vertices with
in-degree equal to i
Keep another array V ertex indexed by the vertices and each entry of that array has a pointer to
where that vertex is in Index.
Keep another array Quarter indexed by vertex to maintain which quarter a subject corresponding
to that vertex is taken. Initialized to 1
Repeat until all the vertices are processed:
If Index[0] is empty return “no schedule possible”.
Take a vertex v from Index[0], return its year.
Remove that vertex from Index[0],
For every edge (v, u), go to V ertex[u]. If u is in Index[i] then remove u from Index[i] and put
it in Index[i-1], set its Quarter[u] = Quarter[v] + 1.
Pseudocode:
The following doubly linked list functions are used below:
1. list.head(L): returns the element at the head of the list L
2. list.remove(L, i): removes the element i from the list L
3. list.add(L, i): adds the element i at the head of the list L
procedure FindGraduationCourseScheduleStudent(G = (V, E), maxQuarters = 12)
Initialize Index, V ertex and Quarter using G, as specified above
repeat
if (Index[0] is empty)
return “No Schedule possible”
v = list.head(Index[0])
if (Quarter[v] > maxQuarters)
return “No Schedule possible”
list.remove(Index[0], v)
for (each edge (v, u) ∈ E):
i = V ertex[u]
list.remove(Index[i], u)

5 of 6
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-1

Index[i-1] = list.add(Index[i-1], u)
Quarter[u] = Quarter[v] + 1
until all vertices v ∈ V are processed
for (vertex v ∈ V )
print “Subject v taken in Quarter Quarter[v]” # Or equivalently, you can use years

Proof of correctness: We will prove this using induction on the maximum number n of quarters
(maxQuarters).
Base case: n = 1
If no vertices in the induced graph G have in-degree of 0 then FindGrauationCourseScheduleStu-
dent() returns “No schedule possible” as index[0] will be empty. If there are courses with in-degree
0 then they will be taken in the first quarter. Any courses with pre-requisites will cause the function
to return “No schedule possible”. Hence, the above implementation will work to find if a student
can graduate in 1 quarter.
Induction Hypothesis: Let’s assume that the above implementation works for n = k quarters, where
k > 1.
Inductive Step: Let us see if this holds for n = k + 1 as well. We have 3 cases:
1. Courses are scheduled such that the student graduates in k quarters.
This is trivial, and works by the induction hypothesis. The student graduates earlier than k + 1
quarters.
2. Courses are scheduled such that the student graduates in k + 1 quarters.
By the induction hypothesis, we are able to find a course schedule for the first k quarters. For
all courses taken in the k th quarter, the first for loop will insert all courses into Index[0] that
had pre-requisites taken in the k th quarter (as i = 1 for all such courses). As such, the set of
courses to be taken in the (k + 1)th quarter will be in Index[0], and the algorithm will assign
Quarter[v] = k + 1 ∀ v ∈ Index[0]. These will also be the last set of courses among all the
courses provided and the process doesn’t repeat beyond this. Hence, we see that this algorithm
works and the student graduates in k + 1 quarters.
3. Courses are scheduled such that the student needs more than k + 1 quarters.
From Case 2, we can see that courses that can be taken in (k + 1) quarters will be correctly
scheduled as per the implementation above. But, as there are some courses whose prerequisites
are taken in the (k + 1)th quarter, the first for loop will add all courses meant to be taken in
the (k + 2)th to Index[0]. Finally, when one of these courses (say, v) is taken from Index[0]
we have that Quarter[v] = k + 2 > k + 1 = n(= maxQuarters) and hence the algorithm will
return “No Schedule possible”. Hence, the algorithm also filters out cases when more time is
needed and the student can’t graduate in a set, maximum number of quarters.
Hence, from induction we see that this implementation will work for any number of quarters, and
should definitely work for the case maxQuarters = 12 whic we are concerned about.

Space Complexity: Assuming that the graph G = (V, E) is represented as an adjacency list, it
occupies space in O(|V | + |E|). The array Index contains doubly linked lists of all vertices in the
graph, and the space occupied by it grows as O(|V |). Even the arrays V ertex and Quarter have
space complexity of O(|V |) as each of them are indexed by the vertices in graph G. Hence, the total
space complexity of this implementation is O(|V | + |E|) + O(|V |) + O(|V |) + O(|V |) = O(|V | + |E|)

6 of 6