School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 307,128
  • Replies: 841,831
  • Topics: 140,681
  • Snippets: 4,468
  • Tutorials: 1,165
  • Total Online: 2,025
  • Members: 113
  • Guests: 1,912

Welcome to Dream.In.Code
Become an Expert!

Join 307,128 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,025 people online right now. Registration is fast and FREE... Join Now!




Algorithm -Rotate a one-dimensional vector of n elements left by d pos

 

Algorithm -Rotate a one-dimensional vector of n elements left by d pos
irishgirl

24 Oct, 2009 - 09:15 AM
Post #1

D.I.C Head
**

Joined: 22 Aug, 2008
Posts: 154



Thanked: 1 times
My Contributions
For instance, with n = 8 and d = 3, the vector abcdefgh is rotated to defghabc. The catch
is that the algorithm may not use a second array or any equivalent as temp storage.

My initial understanding would be to reach the index of d and reverse the top half of the array 'A' to get A,B. Then reverse the latter half after d, the B section, and then finally reverse the entire thing.

Right now I am having some issues expressing this in a linear time divide and conquer algorithm, can anyone give me some helpful pointers in the right direction? Thank you.

User is offlineProfile CardPM
+Quote Post


macosxnerd101

RE: Algorithm -Rotate A One-dimensional Vector Of N Elements Left By D Pos

24 Oct, 2009 - 03:31 PM
Post #2

Self-Trained Economist
Group Icon

Joined: 27 Dec, 2008
Posts: 1,884



Thanked: 208 times
Dream Kudos: 325
Expert In: Java

My Contributions
Try using a dynamic array instead of a static one. Dynamic arrays use the same indexing system as a static array, however, they have certain capabilities of LinkedLists like being able to add elements into the any point in the array without overriding the existing element and the ability to resize. Of course, you can also override an existing element and remove certain elements as well. If you are a Java programmer, you can use the ArrayList class, which is Java's implementation of a Dynamic Array.

For more information on Dynamic Arrays and ArrayLists:
http://en.wikipedia.org/wiki/Dynamic_array
http://java.sun.com/javase/6/docs/api/java.../ArrayList.html
User is offlineProfile CardPM
+Quote Post

LaFayette

RE: Algorithm -Rotate A One-dimensional Vector Of N Elements Left By D Pos

25 Oct, 2009 - 02:20 AM
Post #3

D.I.C Regular
Group Icon

Joined: 24 Nov, 2008
Posts: 258



Thanked: 29 times
Dream Kudos: 25
My Contributions
QUOTE
Try using a dynamic array instead of a static one.


Since this is in Computer Science he's probably not interested in implementation. Also dynamic arrays won't meet he's timing constraint!

At the conquer step, you could given list {a_1, a_2, ... , a_n}, reverse it into {a_n, ..., a_2, a_1} and then recursively reverse (again) {a_n,.., a_n/2} and {a_n/2-1, ..., a_1}. This can be done in-place (constant extra space) pretty straight forward!

edit: Which is pretty much equivalent with your idea also. The only problem is that the whole algorithm will then be O(n*log n). Is it correct that your solution must be linear? Seems kinda though if you can only use O(1) extra storage..

This post has been edited by LaFayette: 25 Oct, 2009 - 02:34 AM
User is offlineProfile CardPM
+Quote Post

Vestah

RE: Algorithm -Rotate A One-dimensional Vector Of N Elements Left By D Pos

25 Oct, 2009 - 05:18 AM
Post #4

New D.I.C Head
Group Icon

Joined: 15 Oct, 2009
Posts: 21



Thanked: 4 times
Dream Kudos: 25
My Contributions
I would firstly let d = d modulo n since there is no need to do the extra rotations.
Storing a single element outside the array will be enough if you want to go through each element placing the right on in that index. This of course would not be a divide-and-conquer, but at least it would be in linear running time with O(1) space consumption.
Maybe you could build upon this where you use some constant k temporary variables which is independent on n and d thus giving O(1) space consumption in regards to n. I'm not really sure if this will work out. It's just my line of thought.
User is offlineProfile CardPM
+Quote Post

irishgirl

RE: Algorithm -Rotate A One-dimensional Vector Of N Elements Left By D Pos

25 Oct, 2009 - 10:38 AM
Post #5

D.I.C Head
**

Joined: 22 Aug, 2008
Posts: 154



Thanked: 1 times
My Contributions
Thanks all, solved!
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 02:31PM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month