advertisement

Intro to Analysis of Algorithms CSE 4081 Points 30 Due: October 10, 2012 W Fall 2012 Home Work 3 Q1. A Pascal Triangle is where each number is a sum of two integers above, starting with 1 on top of the triangle. Here is a sample: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 Write a pseudo-code to generate Pascal numbers up to n-th row, where n is an input integer, first row being n=1. Analyze time and space complexities of your algorithm. [10] Q2. The following is a directed graph G: V= {a, b, c, d, e, f, g, h, i} E= {(a, b), (a, d), (b, c), (c, a), (d, a), (e, d), (i, f), (f, g), (f, h), (g, h), (h, i)} Draw the graph first. Find a sort of the nodes without violating the directions, if there exists any such sort. Otherwise show how the algorithm detects that possibility. [10] Q3. For the following game tree describe which nodes will be pruned by alpha-beta pruning, and explain briefly why they will be pruned? [10]