# Csc263 Assignment Solution

## CSC 263 -- Data Structures

## Fall 2013

*Index of this document*

*Contact information and meeting times*

*Toniann Pitassi*

**Instructor:***Office hours:*Thursday 12-1, or by appointment*Office:*SF 2305A/2302C*Telephone:*416-978-3695/6183*Email:*

**Lecture/tutorial time and location:**Lectures: Thursdays 10-12, LM 161

Tutorials: Tuesday 10-11, LM 161 (NOTE ROOM CHANGE!)

**Back to the index**

*Course content*

*Course goals:**Data structures*are ways of organising the data involved in computation, suitable for representation in and manipulation by computers.

*Algorithms*are precisely stated, general problem solving methods. Data structures and algorithms are central to computer science. They are also integrally related: neither can be studied fruitfully without knowledge of the other.

This course has two goals:* First*, to survey several important data structures and algorithms; and *second*, to introduce the basic tools and techniques for the analysis of algorithms and data structures.

**Cormen, Leiserson, Rivest, and Stein,**

*Required Text:**Introduction to Algorithms*, (

**2nd edition**).

Online access to this text is available free to U of T students through the library website: http://main.library.utoronto.ca/eir/resources.cfm

The

**3rd edition**is available at this website: http://en.tjcities.com/wp-content/uploads/Books/Algorithms_3rd.pdf

*To view the tentative weekly schedule click here .*

**Tentative weekly schedule:**

*Calendar of important course-related events:*Date | Event |

Thurs, Sept 12 | First class |

Mon, Sept 16 | Assignment 1 out |

Tues, Oct 1 | Assignment 1 due and Assignment 2 out |

Tues, Oct 22 | Assignment 2 due |

Tues, Oct 29 | Midterm Exam, Assignment 3 out |

Mon, Nov 4 | Last day to drop F courses |

Mon-Tues, Nov 11-12 | No class (Fall break) |

Thurs, Nov 14 | Assignment 3 due, Assignment 4 out |

Thurs, Nov 28 | Last class, Assignment 4 due |

Final Examination Period | Final Exam |

** Back to the index**

*Course policies*

*There will be four homeworks, a midterm exam and a final exam. The relative weights of these components towards the final mark are shown in the table below:*

**Course evaluation:**Homework | 40% (10% each) |

Midterm | 15% |

Final | 45% |

**Important note:** A mark of at least 35% on the final exam is required to pass the course. Repeated differently: If you receive less than 35% on the final exam, you automatically fail the course, regardless of how well you have done on homeworks or the midterm exam.

*CSC207H1, CSC236H1/CSC238H1/CSC240H1; STA247H1/STA255H1/STA257H1*

**Prerequisites:***For each homework assignment, solutions will be made available.*

**Homework marking:****No late homeworks will be accepted. If you miss a homework deadline because of a medical or personal emergency, you must fill out the Special Consideration Form. (In case of a medical emergency, you must also submit the U of T Student Medical Certificate, completed and signed by your physician.) If we judge your reason for missing the deadline to be valid, we will use the average mark you achieved in other homeworks as your mark for the missed homework.**

*Late homework policy:***Students often learn a lot from working with one another. You are encouraged to meet with other students from class for this purpose. For example, you might work through exercises in the course text together or discuss any material you found confusing in lecture or in the text.**

*Collaboration policy:*It is a good idea to get contact information (email address and telephone number) of at least two other students in the class. That way, if they miss a lecture, you can tell them important information and give them a copy of your lecture notes. They can return the favour if you miss a lecture.

In terms of assignment problems, you may work with zero, or one or two other students who are currently taking the class. If you choose to work in a group (of up to 3 student in total), please submit only one copy of your assignment, with all of your names and student numbers on each page. Assignments must be written up using only the text and your own notes as aids. The point is that your written report should be your own work. Do not let other students outside your group even look at your completed assignment solutions, since this can lead to copying. These rules are meant to ensure that all students understand their solutions to the problems well enough to write up solutions by themselves. Failure to comply with these guidelines is a serious academic offense.

You may not consult any material except the course textbook and your course notes. Note that finding (or copying) the solution to a homework problem on the web does not demonstrate your understanding of course material and, hence, will receive no credit.

**If your request concerns a simple addition error, see the instructor. To make any other kind of remarking request, you must fill this form , attach it to your homework assignment or test, and give it to the instructor of the course no later than one week from the date the marked assignment or test was made available to the class. Remarking requests made after this deadline will not be accepted.**

*Remarking policy:**If you miss the midterm test due to a medical or other serious emergency, get in touch with your instructor immediately, and fill out the Special Consideration Form. (In case of a medical emergency, you must also submit the U of T Student Medical Certificate, completed and signed by your physician.) There will be no make-up test, but if we consider your reason for missing the test to be valid, we will use your final examination mark to compute your mark for the missed midterm test.*

**Missed midterm test policy:***Attendance in tutorials is as mandatory as attendance in lectures. Formal records of attendance will not be taken. However, there will be material that is presented only in tutorial and not discussed in the lectures for which you are responsible and in which you may be tested in homeworks or exams.*

**Attendance in tutorials:***The University of Toronto is committed to accessibility. If you require accomodations or have any accessibility concerns, please visit http://studentlife.utoronto.ca/accessibility as soon as possible or talk to one of the course professors.*

**Accessibility:****Back to the index**

*Announcements*

*In this space we will post announcements related to the course. Please check this space at least weekly. *

**Posted on Sept 9:**The Undergrad Computer Science website https://csc.cdf.toronto.edu contains announcements about things of importance, such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines. I encourage you to read the UGA regularly and to get involved in the great things going on.

**Posted on Sept 10:**Many of you have contacted me about obtaining prerequisite waivers. I will do them together once I get the full list from the undergraduate office, hopefully sometime later this week or early next week.

**Posted on Sept 13:**The tutorials will be held on Tuesdays from 10-11, in BA 1200.

**Posted on Sept 16:**Homework 1 has been posted below. It is due on Oct 1, at the beginning of tutorial.

**Posted on Sept 17:**Please read the homework collaboration policy discussed above. It has changed, reflecting what we discussed in the first lecture.

**Posted on Sept 18:**Accessibility services requires dependable volunteer note-takers to assist students with disabilities in accessing lecture information for this course. Volunteers report that by giving to the U of T community their class attendance and note taking skills improve. Volunteers need to: (1) Register at http://www.studentlife.utoronto.ca/accessibility/pcourselist.aspx or come in person to 215 Huron St. Suite 939; (2) Upload their notes weekly or scan hand written notes. Email at as.notetaking@utoronto.ca or call 416 978 6186 if you have questions or are interested in volunteering. Thanks!

**Posted on Sept 19:**Homework 1 has been updated. (I wrote question 3 in full so that you don't have to look it up in the textbook.)

**Posted on Sept 23:**Extra office hours for HW1 this Thursday 4-5pm, and this Friday 1-2pm in Pratt Room 266.

**Posted on Sept 26:**IMPORTANT: The tutorial room has changed. From now on it will be in the same room as the lecture, LM 161.

**Posted on Sept 27:**Question 2 on HW1 is harder than I anticipated. As a result, you will have an extension for that question. All other problems are still due on Oct 1; question 2 will be due at the same time as HW2 (Oct 22).

**Posted on Sept 30:**Homework 2 has been posted below.

**Posted on Oct 14:**Extra office hours this week, Thursday 3-4pm and Friday 3-4pm in SF3207. Also solutions to HW1 have been posted below.

**Posted on Oct 21:**I am still looking for someone to volunteer to share their class notes with a student registered with disability services. Please see my post above from Sept 18 and *please* consider volunteering. It will not take much of your time, and will be greatly appreciated. Thanks.

**Posted on Oct 24:**My office hours this week will be on Monday, Oct 28, from 12-1 (the day before the test). Office hour on Thursday (Oct 31) will be cancelled.

**Posted on Oct 28:**I mentioned this in the last class, but want to mention it again in case you missed class. PLEASE come to tutorial tomorrow by 9:55am for the test. I will be handing out the test at 10am sharp so that you can have a full hour to complete the test.

**Posted on Oct 29:**Homework 3 has been posted below.

**Posted on Nov 1:**Your grades are available from HW1, HW2 and the midterm. Your raw scores are available under the last 4 digits of your student number here:

- https://docs.google.com/spreadsheet/ccc?key=0AsPskgG0KuM4dFJDbHdxSmw5aDUzNXIxNUFVdmZDNUE&usp=sharing

- To calculate your grade, note that HW1 is out of 50, HW2 is out of 66, and the midterm is out of 55. So if your raw score was A on HW1, B on HW2 and C on the midterm, then your scores as percentages are (A/50)*100, (B/66)*100, and (C/55)*100 respectively. Your assignments and midterm will be available for pickup on Monday from 12-1pm. The marking scheme for question 4 of the midterm is under Handouts below.

**Posted on Nov 6:**Extra office hours on Monday Nov 11 6-7pm in BA3201, and Wednesday Nov 13, 5-7pm in BA3201. Extra clarification for Question 3 on Homework 3 is under Handouts below.

**Posted on Nov 14:**Homework 4 has been posted below. It is due on Nov 28.

**Posted on Nov 18:**Extra office hours on Friday Nov 22 11am-12pm, and Tuesday Nov 26, 4-5pm in BA 3201.

**Posted on Nov 21:**HW4 has been updated and the new version is posted below. The bonus question has been removed, and the ungraded question has been modified. All other questions are unchanged.

**Posted on Nov 24:**Extra office hours this week Tuesday Nov 26, and Wednesday Nov 27, from 4-5pm in BA3201. No office hours on Thursday, Nov 28.

**Posted on Nov 27:**Practice problems for the final exam are posted below. Office hours for the final exam are as follows: Dec 3,4,6,9,10 from 2-3pm in SF3207.

**Posted on Dec 3:**There IS tutorial today! Solutions to HW4 posted below.

**Posted on Dec 8:**You can pick up your graded homeworks and midterm during the remaining office hours, Dec 9, 10 from 2-3pm in SF3207. Grading scheme/comments on HW4 are posted below.

** Back to the index**

*Handouts*

*Handouts*

*In this space we will make available postscript or PDF versions of course material, including homeworks and solutions (posted after the due date, naturally).**To view postscript handouts you will need access to a postscript previewer. If your machine does not have the required software, you can allegedly download it for free by following this link.*

Back to the index

Back to the index

Computer Science CSC263H February 3, 2011St. George Campus University of TorontoSolutions for Homework Assignment #1

Answer to Question 1.

(20 marks)

a.

(6 marks) If the input array is 1

,

2

,

3 then

Build-Max-Heap

transforms it to 3

,

2

,

1 while

Build-by-Inserts

transforms it to 3

,

1

,

2.

b.

(14 marks) Let

T

(

n

) denote the worst-case running time of

Build-by-Inserts

on an input array

A

of size

n

. We must show that

T

(

n

) is Θ(

n

log

2

n

). To do so, we must show that

T

(

n

) is both

O

(

n

log

2

n

)and Ω(

n

log

2

n

).

•

T

(

n

) is

O

(

n

log

2

n

). To show this upper bound on

T

(

n

), note that on every input array

A

of size

n

the loop of

Build-by-Inserts

is executed exactly

n

−

1 times. Each time this loop is executed,it inserts an element into a heap that has

at most

n

elements. Thus, there is a constant

c

suchthat every insertion takes

at most

c

log

2

n

time, and so the

n

−

1 iterations of the loop take

at most

cn

log

2

n

time. We conclude that

T

(

n

) is

O

(

n

log

2

n

).

•

T

(

n

) is Ω(

n

log

2

n

). To show this lower bound on

T

(

n

), consider the execution of

Build-by-Inserts

on an input array

A

of

n

elements such that the

n

elements of

A

appear in increasing order. In thisexecution, for each

j

:1. The

j

th iteration of the loop inserts an element to a heap that already contains

j

elements.2. The

j

th iteration of the loop inserts an element that is larger than any other presently in theheap, and so this element must “percolate up” from the bottom level to the root of the heap.So there is a constant

c

such that for every

j

, the

j

th iteration takes

at least

c

log

2

j

time. Thus,the

n

−

1 iterations take

at least

c

n

−

1

j

=1

log

2

j

time. It turns out that, for all

n

≥

2

8

= 256,

n

−

1

j

=1

log

2

j

≥

116

n

log

2

n

(we include the proof at the end of this solution set). We conclude that,for every

n

≥

256, there is an input array

A

of length

n

for which

BuildNewHeap

takes

at least

c

16

n

log

2

n

time. Thus,

T

(

n

) is Ω(

n

log

2

n

).

Answer to Question 2.

(20 marks)

a.

(8 marks) A binomial heap

H

with

n

vertices consists of

α

(

n

) trees. Let

T

i

, 1

≤

i

≤

α

(

n

), denotethe trees of

H

. A tree

T

i

with

n

i

vertices has

n

i

−

1 edges. So the total number of edges in

H

is

i

=

α

(

n

)

i

=1

(

n

i

−

1) = (

i

=

α

(

n

)

i

=1

n

i

)

−

α

(

n

) =

n

−

α

(

n

)

b.

(12 marks) Binomial heap

H

has

n

nodes before the insertions. By Part (a), it has

n

−

α

(

n

) edgesbefore the insertions. After

k

consecutive insertions,

H

has

n

+

k

nodes, hence it now has (

n

+

k

)

−

α

(

n

+

k

)edges. So the number of new edges created during the

k

consecutive insertions is:[(

n

+

k

)

−

α

(

n

+

k

)]

−

[

n

−

α

(

n

)] =

k

+

α

(

n

)

−

α

(

n

+

k

)

≤

k

+

α

(

n

) edges.As we explained in class, the number of pairwise comparisons between the elements of

H

needed toexecute

k

consecutive insertions is equal to the number of new edges created during these insertions (eachnew edge is the result of a pairwise comparison, and each pairwise comparison creates a new edge in

H

).So

k

consecutive insertions require at most

k

+

α

(

n

) comparisons. By deﬁnition

α

(

n

) is the number of 1’sin the binary representation of

n

, therefore,

α

(

n

)

≤

log

2

n

+ 1. So

k

consecutive insertions require atmost

k

+

log

2

n

+ 1 comparisons. Note that if

k >

log

2

n

,

k

is the dominant factor in

k

+

log

2

n

+ 1.So, when

k >

log

2

n

,

k

consecutive insertions require just

O

(

k

) pairwise comparisons (a constant numberof comparisons per insertion on the average).1

## 0 Replies to “Csc263 Assignment Solution”