Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    2
    ReputationRep:
    Compiled from various, input for corrections and mark allocations appreciated!

    Q1 Matchings Alternating path algorithm to get complete matching in onestep_________________________ ___________________Q2 Shuttle sort- 9- 6 on sixth comparison- 45 total swaps ________________________________ ____________
    Q3 Kruskal’s - 26- 10<x<14 ________________________________ ____________
    Q4 Chinese Postman - Start A finish A: 189 minutes- Passes through vertex D three times- 177- 179- B_______________________________ _____________Q5 Dijkstra’s - J = 15, G = 13- x<4, x>/=3- x=3 ________________________________ ____________Q6 Graph Theory (9 marks)courtesy of shah123Name:  graph theory.jpg
Views: 180
Size:  335.6 KBa) (1 mark)b) (2 marks)c) (2 marks)d) (2 marks)

    ________________________________ ____________Q7 Prims, Travelling Salesman- Prim’s matrix MST = 36- Salesman lower bound = 62- Nearest Neighbour/ upper bounds = 62 and 67- 62 is better upper bound as it is lower so smallerinterval of solutions to salesman problem- Optimal route is 62 as Upper bound = Lower bound___________________________ _________________Q8 Linear programming- 10x+ 15y </= 360 which simplifies to 2x + 3y </=72- OL gradient is -3/4 (Thru y=7.5, x=10 or y=15,x=10, or any other valid I did y=30)- At max vertex, X = 24 and Y = 8- Profit = 15(24) + 20(8) = £520
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What newspaper do you read/prefer?
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.