[go: up one dir, main page]
Scribd
Upload
32 views3 pages

DS F24 Assignment2

Solve this

Uploaded by

emantariq542
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views3 pages

DS F24 Assignment2

Solve this

Uploaded by

emantariq542
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

University of Central Punjab

Faculty of Information Technology and Computer Science

Course Title: Discrete Structures


Course Code: CSAL1213

Assignment 2

Name: _______________________________

Registration Number: ___________________

Section: _____________________________

CLO # Course Learning Outcome (CLO) Taxonomy Mapping


Level to PLO
CLO 3 The students will be able to illustrate the application of C3 PLO 2
mathematical ideas like graphs and trees to computer
science problems.

Instructions:
1. Use first pager as cover page for the assignment.
2. Attempt all questions.
3. Write your answer showing all steps required to perform the task.
4. Assignment must be solved on A4 sheets or Assignment sheets only. Violation will
result to deduction of 10 mark from the scored marks. Submissions will be made
either via portal or in the class.
5. Due Date for Assignment is: 27 November, 2024
6. Late submission will result in 10% deduction in marks.
7. No request for late submissions will be considered after two working days of the
deadline.
No request to review assignment will be considered after 2 working days of the review in
class.
Graphs and Trees

1. Consider the following graph and find the following:


a. The degree of each vertex
b. Make an adjacency list for each vertex

2. Consider the following graph and find the following: (10)


a. Adjacency matrix
b. In-degree and out-degree for each vertex

3. Consider the following graph and find, (10)


a. A Eular path or circuit if there is any
b. A Hamilton path or circuit if there is any

4. A full 5-ary tree has 501 vertices. Find the number of leaves and internal vertices. (10)
5. Draw the spanning tree for this graph by removing the circuits. Draw the spanning tree. (10)

6. The weighted graphs in the figures here show some major


roads in New Jersey. Part (a) shows the distances between
cities on these roads; part (b) shows the tolls.
a) Find a shortest route in distance between Newark and
Camden, and between Newark and Cape May, using these
roads.
b) Find a least expensive route in terms of total tolls using the
roads in the graph between the pairs of cities in part (a) of this
exercise.

7. Use alphabetical order to Build a binary search tree for the


words banana, peach, apple, pear, coconut, mango, and
papaya.
How many comparisons are needed to locate or add each word
in the search tree, starting fresh each time? a) pear
b) banana c) kumquat d) orange

8. Determine the order in which a preorder, inorder and postorder traversal visits the vertices of
the given ordered rooted tree.

You might also like