11-03-2012, 03:18 PM
CS502 Fundamentals of Algorithms Assignment No 1 Fall semester 3rd November 2012
CS 502 Fundamental of Algorithms
Assignment # 01
Fall 2012
Total Marks = 20
Deadline
Your assignment must be uploaded / submitted before or on November 09, 2012
Upload Instructions
Please view the assignment submission process document provided to you by the Virtual University.
Rules for Marking
Please note that your assignment will not be graded if:
It is submitted after due date
The file you uploaded does not open
The file you uploaded is copied from someone else or from internet
It is in some format other than .doc
Note: Material that is an exact copy from handouts or internet would be graded
Zero marks. Your solution should consist of the material found through different sources and written in your own words.
Assignment Statements:
Question 1:
Consider the searching problem:
Input: A sequence of n numbers A = *a1, a2, . . . , an* and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write Pseudo code, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ (lg n).
Question 2:
Describe a Θ (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Promote
4 members promoted this
Share Twitter
Views: 72
Attachments:
Fall 2012_CS502_1.doc Fall 2012_CS502_1.doc, 29 KB
Web hosting services
Running Shoes
Network Social
Social Network
Social Networking
Replies to This Discussion
Permalink Reply by ║ShafiQ KhaN™║ yesterday
Please Discuss here about Assignment no 1.....!
Permalink Reply by + M.Tariq Malik + yesterday
Please Discuss here about this assignment.Thanks
Permalink Reply by AQEEDAT HUSSAIN 2 hours ago
AA friends Please give any idea about the solution of assignment.
RSS
Welcome to
Sign Up
or Sign In
Or sign in with:
University Services
+ VU Orientation
+ Students Handbook
+ Open Courseware
+ VULMS Login Here
+ VU Official Site
+ VU Email
+ Handouts/Books
+ VU Content Library
+ VU Book Shop
+ VU TV Channels
+ VU Contacts List
+ VU Radio
+ Campus Career Portal
+ VU Alumni
+ Vu-Bytes Magazine
+ VU Sports
+ HEC Digital Library
+ VU Lecture Videos
+ We Care
Info
+ 36000+ Members
+ Top Points Members
+ About Us
+ VU Students Team
+ Become a Team Member
+ Moderators Group
+ Top Reputation Members
+ Angels Members
+ Intellectual Members
+ Report an Issue
+ Online Safety
+ Disclaimer
+ Advertise with Us
+ Site FAQ & Rules
Created By: M.Tariq Malik
Designed By: Amel
Chief Admin: M.Tariq Malik
Management: Moderators
+ Awards Badges List
+ Points Ranking System
Like Our Facebook Page